//
//  206. 反转链表.swift
//  Top600
//
//  Created by rjb on 2021/8/3.
//

import Foundation
class Solution206 {
    // 反转链表
    // 采用迭代的解法
    func reverseList(_ head: ListNode?) -> ListNode? {
        var pre: ListNode?
        var cur: ListNode? = head
        while cur != nil {
            let next = cur?.next
            cur?.next = pre
            pre = cur
            cur = next
        }
       return pre
    }
    // 采用递归的写法
    func reverseList2(_ head: ListNode?) -> ListNode? {
        guard let node = head else {
            return head
        }
        guard let _ = node.next else {
            return node
        }
        let ret = reverseList2(node.next)
        node.next?.next = node
        node.next = nil
        return ret
    }

    static func test() {
        let solution = Solution206()
        let node1 = ListNode(1)
        let node2 = ListNode(2)
        let node3 = ListNode(3)
        let node4 = ListNode(4)
        let node5 = ListNode(5)
        
        node1.next = node2
        node2.next = node3
        node3.next = node4
        node4.next = node5
        
        let result = solution.reverseList2(node1)
        print(result)
    }
}
